// 1811.[BFS] 素数行李箱密码 https://oj.rnd.huawei.com/problems/1811/details
//题目详情 提交记录 讨论 代码检视 官方解答
//题目描述
//某行李箱支持 4 位数字密码，每位数字在 0 和 9 之间，开锁方式：
//每次操作改变其中 1 位数字。（注意，是改变，比如0023 改变第4位后，变成 0029）
//每次操作后的数字必须始终是素数（如23和29是素数）。
//现给定行李箱的初始密码与解锁密码（都是素数，包含前导
// 0），请找出最快的开锁方式（改变次数最少），输出改变次数，如果无法解锁，输出
//-1。 输入两个4位数字字符，分别表示初始密码与解锁密码，以单个空格分隔。
//输出一个整数，表示开锁的最少改变次数；无法解锁则输出-1。
//输入 0023 0059
//输出 2
// 0023->0059，存在两种开锁方式：0023->0029->0059，或
// 0023->0053->0059，操作次数都是2 输入 1373 8017 输出 5
// 1373->8017，存在一种开锁方式：1373->0373->0313->0317->8317->8017，需要5次操作
// 0997 1009
// 5
//素数，又称质数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。

#include <bits/stdc++.h>

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

//#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

typedef tuple<string, int, string> PsStat;  // password, count, lastWord

bool isPrime(int tmp) {
  if (tmp < 2) {
    return false;
  }
  for (int i = 2; i <= sqrt(tmp); i++) {
    if (tmp % i == 0) {
      return false;
    }
  }
  return true;
}

// 待实现函数，在此函数中填入答题代码
int Unlock(const string& initState, const string& dstState) {
  if (initState == dstState) {
    return 0;
  }
  queue<PsStat> quState;
  set<string> stVisited;
  quState.push({initState, 0, ""});
  stVisited.insert(initState);
  while (!quState.empty()) {
    auto [curStat, count, preStat] = quState.front();
    quState.pop();
    for (size_t i = 0; i < curStat.length(); i++) {  // 每1位密码/ 4位
      for (unsigned char j = 0; j < 10; j++) {       // 1-9个数字
        string tmp = curStat;
        tmp[i] = '0' + j;
        if (tmp == curStat || stVisited.count(tmp) > 0) {
          continue;
        }
        if (dstState == tmp) {
          PF("PUSH...:%d:%d,....%d\n", stoi(dstState), stoi(curStat),
             count + 1);
          return count + 1;
        }
        if (isPrime(stoi(tmp))) {
          stVisited.insert(tmp);
          quState.push({tmp, count + 1, curStat});
          PF("PUSH:%d,%d..%d\n", stoi(tmp), stoi(curStat), count + 1);
        }
      }
    }
  }
  return -1;
}

// 以下为考题输入输出框架，此部分代码不建议改动
inline std::string ReadWord() {
  std::string word;
  std::cin >> word;
  return word;
}

int main() {
  string initState = ReadWord();
  string dstState = ReadWord();
  cout << Unlock(initState, dstState) << endl;
  return 0;
}
